#pragma once
#include <iostream>

using namespace std;

template <class K, size_t M>
struct BTreeNode
{
    // 为了方便分裂，多给一个位置
    K _keys[M];
    BTreeNode<K, M> *_subs[M + 1];
    BTreeNode<K, M> *_parent;
    // 记录实际存储了多少个关键字
    size_t _n;

    BTreeNode()
    {
        for (size_t i = 0; i < M; ++i)
        {
            _keys[i] = K();
            _subs[i] = nullptr;
        }

        _subs[M] = nullptr;
        _parent = nullptr;
        _n = 0;
    }
};

// 数据是存在磁盘，K是磁盘地址
template <class K, size_t M>
class BTree
{
    typedef BTreeNode<K, M> Node;

public:
    pair<Node *, int> FindNode(const K &key)
    {
        Node *parent = nullptr;
        Node *cur = _root;

        while (cur)
        {
            // 没找到，每次往下一个节点查找，直到查找到的孩子节点为空
            size_t i = 0;
            while (i < cur->_n)
            {
                // 在每一个节点里遍历查找
                if (key < cur->_keys[i])
                {
                    break;
                }
                else if (key > cur->_keys[i])
                {
                    i++;
                }
                else
                {
                    return make_pair(cur, i);
                }
            }

            // 往下一个节点跳
            parent = cur;
            cur = cur->_subs[i];
        }

        return make_pair(parent, -1); // 带回要插入的叶子结点
    }
    void InsertKey(Node *node, const K &key, Node *child)
    {
        int end = node->_n - 1;
        while (end >= 0)
        {
            if (key < node->_keys[end])
            {
                // 挪动key和他的右孩子
                node->_keys[end + 1] = node->_keys[end];
                node->_subs[end + 2] = node->_subs[end + 1];
                end--;
            }
            else
            {
                break;
            }
        }

        node->_keys[end + 1] = key;
        node->_subs[end + 2] = child;

        if (child)
        {
            child->_parent = node;
        }

        node->_n++;
    }
    bool Insert(const K &key)
    {
        // 根不存在
        if (_root == nullptr)
        {
            _root = new Node;
            _root->_keys[0] = key;
            _root->_n++;
            return true;
        }

        // key已经存在 不能再插入
        pair<Node *, int> ret = FindNode(key);
        if (ret.second >= 0)
        {
            return false;
        }

        // 根不存在 循环往parent中进行Key Child的插入
        Node *parent = ret.first;
        K newkey = key;
        Node *child = nullptr;
        while (1)
        {
            InsertKey(parent, newkey, child);
            // 如果插入后没满则返回
            // 满了需要分裂
            if (parent->_n < M)
            {
                return true;
            }
            else
            {
                // 分裂
                //  分裂一半[mid+1, M-1]给兄弟
                size_t mid = M / 2;
                Node *brother = new Node;
                size_t j = 0;
                size_t i = mid + 1;
                for (; i <= M - 1; ++i)
                {
                    // 分裂拷贝key和key的左孩子
                    brother->_keys[j] = parent->_keys[i];
                    brother->_subs[j] = parent->_subs[i];
                    // 如果被拷走的parent的孩子不为空 就要更新该孩子的父亲为兄弟节点
                    if (parent->_subs[i])
                    {
                        parent->_subs[i]->_parent = brother;
                    }
                    ++j;

                    // 拷走重置一下方便观察
                    parent->_keys[i] = K();
                    parent->_subs[i] = nullptr;
                }

                // 还剩下一个右孩子没拷走
                brother->_subs[j] = parent->_subs[i];
                if (parent->_subs[i])
                {
                    parent->_subs[i]->_parent = brother;
                }
                // 重置
                parent->_subs[i] = nullptr;
                // 更新parent和brother中实际关键字的个数
                brother->_n = j;
                parent->_n -= (brother->_n + 1); //+1是因为拷走了一个父亲

                // 中位值
                K midkey = parent->_keys[mid];
                // 重置
                parent->_keys[mid] = K();

                // 判断分裂的是不是根节点
                // 不是根节点在根节点中进行中位数的插入
                if (parent->_parent == nullptr)
                {
                    _root = new Node;
                    _root->_keys[0] = midkey;
                    _root->_subs[0] = parent;
                    _root->_subs[1] = brother;
                    _root->_n = 1;

                    parent->_parent = _root;
                    brother->_parent = _root;

                    break;
                }
                else
                {
                    // 转换成往parent->_parent 去插入parent->[mid] 和 brother
                    newkey = midkey;
                    child = brother;
                    parent = parent->_parent;
                }
            }
        }

        return true;
    }

    void _Inorder(Node* root)
    {
        if(root==nullptr)
        {
            return ;
        }

        for(size_t i=0;i<root->_n;i++)
        {
            //左孩子
            _Inorder(root->_subs[i]);
            //根
            cout<<root->_keys[i]<<endl;
        }

        //最后一个右孩子
        _Inorder(root->_subs[root->_n]);
    }

    void Inorder()
    {
        _Inorder(_root);
    }

private:
    Node *_root = nullptr;
};

void TestBTree()
{
    int a[] = {53, 139, 75, 49, 145, 36, 101};
    BTree<int, 3> t;
    for (auto e : a)
    {
        t.Insert(e);
    }
    t.Inorder();
}